package main.leetcode.clockin.July;

/**
 * 面试题 17.13. 恢复空格
 *
 * <p>哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t
 * boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
 *
 * <p>注意：本题相对原题稍作改动，只需返回未识别的字符数
 *
 * <p>示例：输入： dictionary = ["looked","just","like","her","brother"] sentence =
 * "jesslookedjustliketimherbrother" 输出： 7 解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
 *
 * <p>提示：0 <= len(sentence) <= 1000 dictionary中总字符数不超过 150000。 你可以认为dictionary和sentence中只包含小写字母。
 */
public class day9 {
    public static void main(String[] args) {
        System.out.println(
                new day9()
                        .respace(
                                new String[] {"looked", "just", "like", "her", "brother"},
                                "jesslookedjustliketimherbrother"));
    }

    //    public int respace(String[] dictionary, String sentence) {
    //        HashSet<String> set = new HashSet<>(Arrays.asList(dictionary));
    //        int n = sentence.length();
    //        int[] dp = new int[n + 1];
    //        for (int i = 1; i <= n; ++i) {
    //            dp[i] = dp[i - 1] + 1;
    //            for (int j = 0; j < i; ++j) {
    //                if (set.contains(sentence.substring(j, i))) {
    //                    dp[i] = Math.min(dp[i], dp[j]);
    //                }
    //            }
    //        }
    //        return dp[n];
    //    }

    public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();
        Trie root = new Trie();
        for (String s : dictionary) {
            root.insert(s);
        }
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + 1;
            Trie cur = root;
            for (int j = i; j > 0; --j) {
                int pos = sentence.charAt(j - 1) - 'a';
                if (cur.next[pos] == null) {
                    break;
                }
                if (cur.next[pos].isEnd) {
                    dp[i] = Math.min(dp[i], dp[j - 1]);
                }
                // dp[i] == 0 意味着i之前没有无法识别的单词，所以可以剪枝
                if (dp[i] == 0) {
                    break;
                }
                cur = cur.next[pos];
            }
        }
        return dp[n];
    }

    static class Trie {
        private Trie[] next;
        private boolean isEnd;

        Trie() {
            next = new Trie[26];
            isEnd = false;
        }

        void insert(String s) {
            Trie cur = this;
            char[] chars = s.toCharArray();
            for (int i = chars.length - 1; i >= 0; --i) {
                int pos = chars[i] - 'a';
                if (cur.next[pos] == null) {
                    cur.next[pos] = new Trie();
                }
                cur = cur.next[pos];
            }
            cur.isEnd = true;
        }
    }
}
